Traditional memory devices are accessed by specifying an address of one or more particular locations within the memory, and the data stored at these locations is retrieved from the memory. On the other hand, an associative memory is a memory device or system that can be accessed by searching for matching content rather than by specifying a memory address. Generally, the information stored in an associative memory is accessed by comparing an input, or search key, with the “comparand” of each entry stored in the memory. If the search key matches the comparand of an entry, the associative memory will return the data stored in that entry. The data associated with an entry may include a memory address (to a memory location where data associated with the entry is stored), as well as any other types of data. If multiple entries of the associative memory match the search key, the associative memory will typically return the entry having the highest priority. Priority of an entry in the associative memory may be determined by the position of that entry in the memory or by a priority value stored as part of that entry. Associative memories are used in a variety of applications, including routing tables for matching destination addresses (e.g., Internet Protocol, or IP, addresses) and look-up tables in packet classification engines, as well as other database applications.
One type of associative memory is content addressable memory (CAM), and there are two common types of CAM devices: binary CAMs and ternary CAMs. A binary CAM requires an exact match between all bits of the search key and all bits of a comparand in order for a match to occur. A ternary CAM allows a comparand to be expressed as a range, wherein masked bits represent “don't care” bits that are ignored in the comparison process and that are essentially filtered from the comparand. For example, the comparand “100101XX” has two masked bits (each represented by an “X”) and spans a range from 10010100 to 10010111. The range of a comparand in a ternary CAM is a binary range, which is a range extending from a lower bound (LB) of LB=(a)(2m) to an upper bound (UB) of UB=(a+1)(2m)−1, where “a” is an integer.
Another type of associative memory is boundary addressable memory (BAM). The comparand of an entry of a BAM device includes a lower bound (LB) and an upper bound (UB), and the comparand spans a range from the LB to the UB. There is, however, no requirement that the upper and lower bounds have any relation to a power of “2”—a requirement of ternary CAMs, where ranges are expressed using the same power of “2” (e.g., 2m), as noted above—and such ranges are referred to herein as “arithmetic” or “non-binary” ranges.
Referring now to FIG. 1, illustrated is an embodiment of an associative memory system 100. The system 100 includes a search client 110, an associative memory cache 120, and a primary associative memory 130. The search client 110 may comprise a processing device (e.g., a network processor) or a processing system. The associative memory cache 120 may comprise any type of associative memory, such as a CAM or a BAM. Likewise, the primary associative memory 130 may comprise any suitable type of associative memory, including a CAM or BAM, as well as any equivalent implementation, such as an algorithmic search of a static random access memory (SRAM) or a dynamic random access memory (DRAM). In addition to the associative memory cache 120 shown in FIG. 1, the system 100 may include additional levels of associative memory cache.
During operation, the search client 110 sends search requests to the associative memory cache 120, and if the associative memory cache 120 has the requested data—i.e., a cache “hit”—the associative memory cache provides the data to the search client 110. Conversely, if the associative memory cache 120 does not have an entry that matches the search request—i.e., a cache “miss” the primary associative memory 130 is accessed to query whether this memory contains the needed data. If the primary associative memory 130 has an entry matching the search request, the data is forwarded to the search client 110.
When multiple entries in the primary associative memory 130 match the search request, the primary associative memory will generally return the highest priority matching entry. In addition, because the primary associative memory 130 can store comparands expressed as ranges, there may be one or more entries in the primary associative memory that have ranges overlapping the range of the highest priority matching entry. As used herein, the term “overlapping” indicates that the comparands of two or more entries will map to ranges that overlap one another. In prior implementations, in order to ensure correct results after a cache miss, those overlapping entries having a priority greater than that of the matching entry would also be returned by the primary associative memory 130 along with the highest priority matching entry, and the highest priority and higher priority overlapping entries would all be entered into the associative memory cache 120.
Returning all higher priority overlapping entries and the highest priority matching entry does, however, necessitate a large associative memory cache and, further, updating the cache to include these multiple new entries requires more complex replacement algorithms to determine which existing cache entries can be replaced. Also, because the highest priority matching entry is cached along with one or more higher priority overlapping entries, if a subsequent search falls in a range covered by two or more of these entries, multiple matches will result. The associative memory cache will, therefore, need priority resolution logic to determine which of these multiple matching entries has the higher priority.